(copyright) 2001 Intransit Networks, Inc. A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. 37 CFR 1.71 (e).
The present invention relates to methods of forming ad hoc data communication networks and distributed databases and, in particular, to methods of dynamic self-organization of wireless transceivers based on classes of articles associated with the wireless transceivers to form hierarchical ad hoc wireless data communication networks and distributed databases.
Wireless ad hoc networks allow node-to-node communication without central control or wired infrastructure. Such networks may have dynamic, randomly-changing, multihop topologies composed of wireless data communication links between the nodes. Ad hoc networks are advantageous because they are inexpensive, fault-tolerant, and flexible. Various known methods relate to data transmission within an ad hoc wireless data communication network. However, most known methods do not address self-configuration of wireless nodes for the formation and maintenance of efficient network topology.
Short range wireless technology such as the Bluetooth(trademark) radio standard promises to remove price barriers to mobile network use. By doing so, wireless devices are becoming available for applications where wired networks have been impracticable and in which prior wireless communication networks have been too expensive or inflexible. While Bluetooth radio technology is an ad hoc networking solution for personal data applications, it provides for only a limited number of communication channels, thereby restricting the number of Bluetooth devices that will communicate over an ad hoc network at any given time. Thus a need exists for an improved low cost networking technology that has the benefits of the Bluetooth price and flexibility, while overcoming the limited networking capacity of typical Bluetooth technology.
Known ad hoc networking methods typically organize the network on the basis of geographic proximity of the nodes or the strength of signals received by the various nodes. While geographical organization or signal strength organization may work well for some applications, many others are limited. Known methods of ad hoc network organization also require nodes to regularly transmit network information to all other nodes in the network, which results in increased radio traffic and interference. Increased radio interference inhibits the formation and maintenance of ad hoc networks having a large number of nodes and requires nodes to transmit at a greater power, which reduces their battery life. Thus a need exists for more efficient methods of forming, organizing, and maintaining ad hoc wireless networks.
Wireless data networks are known for use in warehouse management and other asset tracking applications. However, existing wireless data network technologies are not well suited to asset tracking, which involves a large number of network nodes (e.g., hundreds and thousands). Furthermore, existing wireless technologies are cost prohibitive, are prone to RF interference, and consume a large amount of electrical power. Thus a need exists for a wireless data network technology that accommodates a large number of nodes, creates less RF interference, and consumes less power.
In accordance with the present invention, a method of forming an ad hoc hierarchical wireless data communication network involves associating a plurality of wireless transceivers with articles to be tracked, and assigning to each of the transceivers a xe2x80x9cclass designationxe2x80x9d representative of a characteristic or behavior of the article with which the transceiver is associated. Each of the wireless transceivers includes a network organization routine that operates in coordination with the network organization routines of other transceivers to establish the hierarchical network based on the transceivers"" class designations. The hierarchical network provides an efficient topology for selective communication among wireless transceivers of the same class. The ad hoc network organization routines are preferably implemented in software operable on a digital processor of the wireless transceivers. Alternatively, the ad hoc network organization routines may be implemented in other ways, such as hardwired logic circuitry.
Each wireless transceiver""s class designation assignment is included in a profile that is stored in a memory readable by the digital processor of the wireless transceiver. Alternatively, the class designation may be set in hardwired or programmable logic circuitry. Depending on user needs and preferences, the class designation may represent an abstract class of article, such as a ball; a subclass of the class, such as a soccer ball; or a subclass of the subclass (a sub-subclass), such as a size 5 soccer ball, etc. When the class designation represents a subclass, it may also include information about the class or classes abstracted from the subclass, e.g., /ball/soccer_ball/sizexe2x80x945_soccer_ball. Alternatively, the wireless transceiver""s class designation may be intentionally limited to subclass (/sizexe2x80x945_soccer_ball), while information about the subclass"" abstract class is represented in memory on the transceiver or remotely from the transceiver in class dictionaries or rule sets. In addition to the current class designation, the profile may include auxiliary information such as, for example, a characteristic of the associated article (e.g., serial number, status, process step, physical location, color, size, density, etc.), a behavior of the associated article (e.g., temperature sensitivity, light sensitivity, shelf life, etc.), sensor derived information (e.g., temperature, humidity, altitude, pressure, etc.), a rank of the wireless transceiver in the hierarchical network (e.g., primary (xe2x80x9cmasterxe2x80x9d), secondary (xe2x80x9cslavexe2x80x9d), sub-primary, tertiary, etc.), a priority designation to provide improved response to selected transceivers, a privilege level (e.g., visitor, employee, manager, administrator, super user, etc.), and time-sensitive information (e.g., synchronization timing, real-time sensor data, GPS data, etc.).
The profile and, in particular, the class designation are used by the wireless transceiver to selectively receive packets intended for receipt by transceivers of the same class designation (including/class/subclass). Typically, messages or commands are transmitted to a class (or subclass) of nodes by broadcasting or multicasting the commands in packets that begin with a preamble including the class designation information and possibly other profile information. Transceivers within range of the transmitting transceiver will wake up from a standby mode to receive and process an entire packet only when the packet""s preamble matches the receiving transceiver""s class designation.
In a preferred embodiment, each of the wireless transceivers includes a low-power radio frequency device (xe2x80x9cLPRFxe2x80x9d), which operates in accordance with the Bluetooth(trademark) system specification. It should be understood that the invention is not limited to use with Bluetooth(trademark) technology, but can be used with any wireless transceiver having the capability to communicate directly with multiple other wireless transceivers, such as wireless ethernet transceivers, 802.11, Home RF, and others. The term xe2x80x9cLPRFxe2x80x9d as used herein refers generally to a two-way wireless radio-frequency data communication device that transmits data in packets, and is not limited to a particular signal strength or power consumption.
The self-configuration routines used to form ad hoc class-based networks in accordance with the present invention may also be used to perform autonomous modification and reconfiguration of such networks in response to changes in the location, status, behavior, characteristics or class designation of articles associated with the transceivers. Similarly, the self-configuration methods of the present invention facilitate maintenance of radio communication links in response to changes in the operational characteristics of the wireless transceivers and radio frequency transponders that comprise the network fabric. For example, self-configuration routines are responsive to changes caused by battery drain, radio transmitter failures, radio interference, and digital processor failure, by their inherent methods of organizing the network to have optimal link integrity and node connectivity.
In one aspect of the invention, a class adoption step involves an adopting one of the LPRF units that detects the class designation of one or more nearby radio frequency transponders (also known as radio-frequency identification tags, RFID Tags, or RFTs) or of nearby LPRFs, and incorporates the detected class designation in its own profile. Typically, class adoption is performed only when the adopting LPRF is unable to participate in the ad hoc hierarchical network because of a missing or corrupted class designation. In some circumstances, class adoption may be useful even if the adopting LPRF has sufficient class designation information to support communication. For example, an LPRF attached to a pallet could periodically update its class by detecting the classes of nearby LPRF and RFID Tags (e.g., those attached to items placed on the pallet). Alternatively an LPRF unit can be manually programmed with a class designation by use of a handheld interrogator module (xe2x80x9cHIMxe2x80x9d). The HIM is a sort of remote control device that allows a human operator to program LPRF units and to query LPRF and RFT units. Preferably, the HIM includes an LPRF unit that is controlled by application software designed to facilitate manual human interaction and communication with nearby LPRF and RFT units.
In another aspect of the invention, a network interface module (xe2x80x9cNIMxe2x80x9d) serves as a communication gateway between the ad hoc hierarchical network and an external network such as a local area network (LAN), wide area network (WAN), or the Internet. The NIM includes at least a NIM RF unit for communication with LPRF nodes of the ad hoc network and an external network interface for connecting the NIM RF unit to the external network. A server computer that is typically connected to the external network includes communication interfaces for directing messages and instructions, via the NIM, to selected classes of LPRFs of the ad hoc network. Conversely, LPRFs of the ad hoc network can direct messages and instructions to the server via the NIM.
In conjunction with the server, class-switching facilitates automated and semi-automated segregation, tracking, monitoring, and delivery of assets. The server issues, via the NIM, class-directed messages and class-directed queries to monitor and track a class of LPRF units. User-defined class granularity facilitates the use of separate sub-classes for various attributes and states of the articles, e.g., production batches, phases of production, and the delivery process. By increasing granularity, i.e., using many subclasses (including sub-subclasses, etc.), control commands and messages from the server can be directed to only those subclasses of interest, rather than all LPRF units. Furthermore, because messages and control commands are transmitted in packets that include in their preambles the class/subclass destination, the LPRF radios excluded from the class do not wake up from standby mode to receive the packets and do not acknowledge or reply to the packets. This reduces radio interference and power consumption while making asset tracking functions more efficient.
In yet another aspect of the invention, the class-based ad hoc network serves as a dynamic distributed hierarchical database system. In this aspect of the invention, transceivers and RFTs include a query handling routine in communication with a memory of the transceiver or RFT. The query handling routine interprets and responds to class-directed database queries and update transaction requests, for example, from an HIM or a server-based asset tracking application operating on the external network. Database queries may include status queries that gather up-to-date status information about the articles. Profile update transaction requests may include requests to change profile data on specified transceivers of the distributed database system. Increased class granularity also facilitates improved data retrieval efficiency in the distributed database system by reducing the number of transceivers that must be involved in a profile query or update transaction.
Additional aspects and advantages of this invention will be apparent from the following detailed description of preferred embodiments thereof, which proceeds with reference to the accompanying drawings.